/*
===========================================================================
This source file is part of DyLab (Dynamic Laboratory)
For the latest info, see http://dylab.googlecode.com

Copyright (c) 2006-2008 Lukas Krejci
(krejci.lukas@volny.cz)

This file is part of DyLab.

    DyLab is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    DyLab is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with DyLab.  If not, see <http://www.gnu.org/licenses/>.
===========================================================================
*/

#ifndef __dylab_ArrayList_h__
#define __dylab_ArrayList_h__

//===========================================================================================
#include <map>

//===========================================================================================
#include <dylab/utils/exceptions/EInvalidArgument.h>

//===========================================================================================
namespace dylab {

    /** Linear pool of ElementTypes without fixed capacity. 
	@deprecated
		This implementation of this structure is not thread nor object safe
		and thus will be removed in the future releases.
		Better, thread safe alternative is VectorContainer or VectorObjContainer.
	@warning
		The ElementType shouldn't be class (struct is ok) since no constructor is called 
		no virtual tables are constructed during its allocation, 
		and no destructor is called at its deallocation.
    */
    template < typename ElementType >
    class ArrayList 
    {
    private:

        ///
        typedef std::map < uint32_t, uint32_t > FreeIndexTupleMap;
        typedef FreeIndexTupleMap::iterator FreeIndexTupleMapIt;
        typedef typename FreeIndexTupleMap::const_iterator FreeIndexTupleMapConstIt;

    private:

        /** pointer to the linear data container memory block */
        ElementType * mArray;

        /** current number of elements stored in container */
        uint32_t mElementCount;

        /**
         * current container's storage capacity for its elements
         * @remarks: if more capacity is desired, then the current value is doubled
         */
        uint32_t mCapacity;

        /**
         * vector field of currently available free indeices
         * @remarks: preferentially, if not empty, its front items are used as indices to populate the container with new elements
         */
        FreeIndexTupleMap mFreeIndexTupleMap;

    public:

        /** 
         * initializes the container's attributes 
         */
        ArrayList() 
            : mArray(NULL), mElementCount(0), mCapacity(0) 
                { }

        /** 
         * releases all of container's allocated memory 
         */
        ~ArrayList() 
                { mFreeIndexTupleMap.clear(); }

        /** 
         * returns the current number of elements stored in the container 
         */
        uint32_t getElementCount() const 
                { return mElementCount; }

        /**  
         * adjusts the array list capacity (in elements) so that the list can contain 
         * at least minCapacity elements
         */
        void adjustCapacity(uint32_t minCapacity) 
                {
                    uint32_t newCapacity = mCapacity;
                    if (newCapacity < minCapacity) { // grow the buffer (double its size)
                        if (newCapacity == 0)
                            newCapacity = 1;
                        while (newCapacity < minCapacity)
                             newCapacity <<= 1;
                    }
                    else if (newCapacity>>1 > minCapacity) {  // shrink the buffer (to the half of its size)
                        while (newCapacity>>1 > minCapacity)
                            newCapacity >>= 1;
                    }
                    if (newCapacity != mCapacity) { // the buffer size is to be changed
                        mCapacity = newCapacity;
                        mArray = static_cast<ElementType*>(realloc(static_cast<void*>(mArray), mCapacity*sizeof(ElementType)));
                        DYLAB_ASSERT(mArray != NULL);                
                    }
                }

        /** 
         * returns the current capacity of the container (i.e., number of elements, 
         * that can be stored without re-allocation) 
         */
        uint32_t getCapacity() const 
                { return mCapacity; }

        /**
         * creates new elements and returns index position of the first one in this container
         * @remarks:    the new created elements form an continguos array
         *              new element's data are NOT initialised to any value nor zeroed
         */
        uint32_t addElements(uint32_t newElementCount = 1) 
                {
                    uint32_t index = 0;
                    bool freeIndexFound = false;
                    for (FreeIndexTupleMapIt it = mFreeIndexTupleMap.begin(); it != mFreeIndexTupleMap.end(); ++it) {
                        if (it->second == newElementCount) {    // tuple size match, populate this free tuple
                            index = it->first;
                            mFreeIndexTupleMap.erase(it);
                            freeIndexFound = true;
                        }
                    }
                    if (!freeIndexFound) {  // there is no free index with equal tuple size
                        index = mElementCount;                                
                        adjustCapacity(mElementCount + newElementCount);
                    }            
                    mElementCount += newElementCount;
                    return index;
                }

        /**
         * Returns reference to the element given by its index.
         * @return: Returns reference to the element given by its index.
         * @remark: The element must exists prior to calling this method.
         */
        ElementType & getElement(uint32_t index) 
                {
                    if (!isOccupied(index)) 
                        throw EInvalidArgument(String::fmt("Specified index (%1%) is not occupied.", index));

                    return * (mArray + index);
                }

        /**
         * Returns pointer to the element given by its index.
         * @return: Returns pointer to the element given by its index.
         * @remark: The element must exists prior to calling this method.
         */
        ElementType * getElementPtr(uint32_t index) 
                {
                    if (!isOccupied(index)) 
                        throw EInvalidArgument(String::fmt("Specified index (%1%) is not occupied.", index));

                    return (mArray + index);
                }

        /**
         * Alias for the getElement method.
         */
        ElementType & operator[] (uint32_t index) 
                { return getElement(index); }

        /**
         * Returns reference to the const element given by its index.
         * @return: Returns reference to the element given by its index.
         * @remark: The element must exists prior to calling this method.
         */
        const ElementType & getConstElement(uint32_t index) const 
                {
                    if (!isOccupied(index)) 
                        throw EInvalidArgument(String::fmt("Specified index (%1%) is not occupied.", index));

                    return * (mArray + index);
                }

        /**
         * removes element given by its index.
         * @remarks: the index is from now treated as free, and could be assigned to newly created elements
         */
        void removeElements(uint32_t index, uint32_t removeElementCount = 1) 
                {
                    if (!isOccupied(index, removeElementCount)) 
                        throw EInvalidArgument(String::fmt("Specified elements (%2%) from the index (%1%) are not occupied.", index, removeElementCount));

                    mElementCount -= removeElementCount;
                    if (index == mElementCount) // the removed element is at the end of the list
                        adjustCapacity(mElementCount);
                    else
                        mFreeIndexTupleMap[index] = removeElementCount; // so add the removed tuple index to the free indices
                }

        /** 
         * returns true, if an element tuple occupies the buffer from the given index, otherwise returns false 
         */
        bool isOccupied(uint32_t index, uint32_t elementCount = 1) const 
                { return (index + elementCount - 1 < mElementCount) && !_isFreeIndexTuple(index, elementCount); }

        /** 
         * returns true if the container has holes, i.e., some of the front or inner element 
         * cells are not occupied 
         */
        bool hasHoles() const 
                { return !mFreeIndexTupleMap.empty(); }

        /**
         * Returns pointer to the array containing the list elements.
         * @remark: The array should not contain any holes.
         */
        ElementType * getArrayPtr() 
                {
                    DYLAB_ASSERT(mArray != NULL);
                    DYLAB_ASSERT(!hasHoles());   // is it really necessary?
                    return mArray;
                }

        /**
         * Returns pointer to the const array containing the list elements.
         * @remark: The array should not contain any holes.
         */
        const ElementType * getConstArrayPtr() const 
                {
                    DYLAB_ASSERT(mArray != NULL);
                    DYLAB_ASSERT(!hasHoles());   
                    return mArray;
                }

    private:

        /** 
         * returns true, if the given index is known to be free, otherwise returns false 
         */
        bool _isFreeIndexTuple(uint32_t index, uint32_t elementCount) const 
                {
                    for (FreeIndexTupleMapConstIt it = mFreeIndexTupleMap.begin(); it != mFreeIndexTupleMap.end(); ++it) {
                        if (it->first == index && it->second == elementCount)
                            return true;
                    }
                    return false;
                }
        
    };
}
//===========================================================================================
#endif // __dylab_ArrayList_h__
